Mi manual de algoritmos/version_maraton_nacional_2008/src/grafos/ford_fulkerson.cpp

   1 int cap[MAXN+1][MAXN+1], flow[MAXN+1][MAXN+1], prev[MAXN+1];
   2
   3 /*
   4   cap[i][j] = Capacidad de la arista (i, j).
   5   flow[i][j] = Flujo actual de i a j.
   6   prev[i] = Predecesor del nodo i en un camino de aumentación.
   7  */
   8
   9 int fordFulkerson(int n, int s, int t){
  10   int ans = 0;
  11   for (int i=0; i<n; ++i) fill(flow[i], flow[i]+n, 0);
  12   while (true){
  13     fill(prev, prev+n, -1);
  14     queue<int> q;
  15     q.push(s);
  16     while (q.size() && prev[t] == -1){
  17       int u = q.front();
  18       q.pop();
  19       for (int v = 0; v<n; ++v)
  20         if ( v != s && prev[v] == -1 && cap[u][v] > flow[u][v] )
  21           prev[v] = u, q.push(v);
  22     }
  23
  24     if (prev[t] == -1) break;
  25
  26     int bottleneck = INT_MAX;
  27     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  28       bottleneck = min(bottleneck, cap[u][v] - flow[u][v]);
  29     }
  30     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  31       flow[u][v] += bottleneck;
  32       flow[v][u] = -flow[u][v];
  33     }
  34     ans += bottleneck;
  35   }
  36   return ans;
  37 }